package Leetcode;

public class problem28 {
    public int strStr(String haystack, String needle) {

        if( needle.length() == 0){
            return 0;
        }

        int i = 0;
        int j = 0;

        int[] next = getNext(needle);

        while(i < haystack.length() && j < needle.length()){
            if(j == -1 || haystack.charAt(i) == needle.charAt(j)){
                i++;
                j++;
            }else{
                //i = i - j + 1;
                j = next[j];
            }
        }

        if(j == needle.length()){
            return i - j;
        }

        return -1;

    }

    public int[] getNext(String needle){

        int[] arr = new int[needle.length()];
        char[] str = needle.toCharArray();

        int j = 0;
        int k = -1;
        arr[0] = -1;

        while(j < str.length - 1){
            if(k == -1 || str[j] == str[k]){
                arr[++j] = ++k;
            }else{
                k = arr[k];
            }
        }

        return arr;
    }

}
